package com.wengu.linkedlist;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import org.junit.jupiter.api.Test;
import sun.applet.AppletIllegalArgumentException;

import javax.sound.midi.Soundbank;

/**
 * 约瑟夫问题
 *
 * @Author 王海雷
 * @Date 2021/6/27 18:17
 * @Version 1.0
 */
public class JosephusDemo {

    @Test
    public void test1() {
        CircleLinkedList list = new CircleLinkedList();
        list.add(new PersonNode(1,null));
        list.add(new PersonNode(2,null));
        list.add(new PersonNode(3,null));

        list.showList();
    }

    @Test
    public void test2() {
        CircleLinkedList list = new CircleLinkedList(5);

        list.showList();
    }

    @Test
    public void test3(){
        CircleLinkedList.solveJosephus(5,3,2);
    }

    @Test
    public void test4(){
        CircleLinkedList2 list = new CircleLinkedList2();
        list.add(new CircleNode(1,4));
//        list.add(new CircleNode(2,6));
//        list.add(new CircleNode(3,2));
        list.showList();
    }

    @Test
    public void test5(){
        CircleLinkedList2 list = new CircleLinkedList2();
        list.addBatch(3,100);
        list.showList();
    }

    @Test
    public void test6(){
        CircleLinkedList2 list = new CircleLinkedList2(3,100);
        list.showList();
    }

    @Test
    public void test7(){
        CircleLinkedList2 list = new CircleLinkedList2();
        list.solveJosephus(5,2,2,5);
//        list.showList();
    }
}

class CircleLinkedList2 {
    private CircleNode head;

    public CircleLinkedList2(){
        head = new CircleNode(0,0);
    }

    public CircleLinkedList2(int num,int randomKey){
        this();
        this.addBatch(num,randomKey);
    }

    /**
     * 加强版约瑟夫问题："密码问题"
     * 问题描述：编号为1、2、3、...、N的N个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。从指定
     * 编号为k的人开始，按顺时针方向自1开始顺序报数，报到指定数M时停止报数，报M的人出列，并将
     * 他的密码作为新的M值，从他在顺时针方向的下一个人开始，重新从1报数，依此类推，直至所有的
     * 人全部出列为止。请设计一个程序求出出列的顺序，其中密码值随机生成。
     *
     * @param n 节点个数
     * @param k 从第k个节点开始报数
     * @param randomKey 随机值的范围值
     */
    public void solveJosephus(int n,int k,int m,int randomKey){
        if (n < 2){
            throw new RuntimeException("环节列表节点数量必须大于2");
        }
        if (n < k){
            throw new RuntimeException("k值不能大于环形列表节点数量");
        }
        this.addBatch(n,randomKey);
        // 定义当前元素和前一元素的指针
        CircleNode cur;
        CircleNode pre;
        // 定义密码值，也就是题中的M
        cur = head.getNext();
        pre = head.getNext();
        for (int i = 0; i < n - 1; i++) {
            pre = pre.getNext();
        }
        if (k != 1){
            for (int i = 0; i < k - 1; i++) {
                cur = cur.getNext();
                pre = pre.getNext();
            }
        }
        System.out.println("移除的对象的顺序是：");
        // 执行报数后离队的操作
        while (true){
            if (pre == cur){
                break;
            }
            // 报数
            for (int i = 0; i < m - 1; i++) {
                cur = cur.getNext();
                pre = pre.getNext();
            }
            // 将密码值赋值给m
            m = cur.getKey();
            System.out.println(" -> " + cur);
            // 移除数到m的节点
            cur = cur.getNext();
            pre.setNext(cur);
        }
        System.out.println(" -> " + cur);

    }
    public void addBatch(int num,int randomKey){
        if (num <= 0){
            throw new RuntimeException("环形列表节点数不能小于0");
        }
        CircleNode temp = head;
        for (int i = 1; i <= num; i++) {
            temp.setNext(new CircleNode(i,(int) (Math.random()*randomKey + 1)));
            temp = temp.getNext();
        }
        temp.setNext(head.getNext());
    }

    /**
     * 在尾部插入元素
     * @param node
     */
    public void add(CircleNode node){
        if (head.getNext() == null){
            head.setNext(node);
            node.setNext(node);
        } else {
            CircleNode temp = head.getNext();
            while (true){
                if (temp.getNext() == head.getNext()){
                    break;
                }
                temp = temp.getNext();
            }
            temp.setNext(node);
            node.setNext(head.getNext());
        }
    }

    /**
     * 遍历环形列表
     */
    public void showList(){
        if (head.getNext() == null){
            System.out.println("该环形列表为空");
        } else {
            CircleNode temp = head.getNext();
            while (true){
                System.out.println(temp);
                temp = temp.getNext();
                if (temp == head.getNext()) break;
            }
        }
    }
}

@Data
@NoArgsConstructor
class CircleNode {
    private int no;
    private int key;
    private CircleNode next;

    public CircleNode(int no,int key){
        this.no = no;
        this.key = key;
    }

    @Override
    public String toString() {
        return "CircleNode{" +
                "no=" + no +
                ",key=" + key +
                '}';
    }
}


class CircleLinkedList {
    private PersonNode head;

    public CircleLinkedList() {
        head = new PersonNode(0, null);
    }

    /**
     * 初始化时多个节点构造器
     *
     * @param num 节点数量
     */
    public CircleLinkedList(int num) {
        head = new PersonNode(0, null);
        PersonNode temp = head;
        for (int i = 1; i <= num; i++) {
            PersonNode node = new PersonNode(i, head.getNext());
            temp.setNext(node);
            temp = temp.getNext();
        }
    }

    /**
     *
     * @param num 环节列表的元素个数
     * @param k 从第k个节点开始报数
     * @param m 报数的大小
     */
    public static void solveJosephus(int num,int k,int m){
        if (num < k){
            throw new RuntimeException("k不能大于总节点数");
        }
        if (num < 2){
            throw new RuntimeException("总节点数不能小于2");
        }
        CircleLinkedList list = new CircleLinkedList(num);
        // 当前节点
        PersonNode curr ;
        // 上一节点
        PersonNode pre ;
        PersonNode head = list.head;
        // 初始化指针位置
        if (k == 1){
            curr = head.getNext();
            pre = head.getNext();
            for (int i = 0; i < num - 1; i++) {
                pre = pre.getNext();
            }
        }else{
            curr = head.getNext().getNext();
            pre = head.getNext();
            for (int i = 0; i < k - 2; i++) {
                curr = curr.getNext();
                pre = pre.getNext();
            }
        }
        // 开始报数
        System.out.print("出队顺序：");
        for (int i = 0; i < num - 1; i++) {
            for (int j = 0; j < m - 1; j++) {
                curr = curr.getNext();
                pre = pre.getNext();
            }
            System.out.print(curr.getNo() + " -> ");
            curr = curr.getNext();
            pre.setNext(curr);
        }
        System.out.print(curr.getNo());
    }

    /**
     * 添加方法
     *
     * @param node
     */
    public void add(PersonNode node) {
        PersonNode temp = head.getNext();
        while (true) {
            if (temp == null) {
                head.setNext(node);
                node.setNext(node);
                break;
            }
            if (temp.getNext() == head.getNext()) {
                temp.setNext(node);
                node.setNext(head.getNext());
                break;
            }
            temp = temp.getNext();
        }
    }

    public void showList() {
        PersonNode temp = head.getNext();
        while (true) {
            if (temp == null) {
                System.out.println("该环形列表为空！");
                break;
            }
            System.out.println(temp);
            temp = temp.getNext();
            if (temp == head.getNext()) {
                break;
            }
        }

    }


}

@Data
@NoArgsConstructor
@AllArgsConstructor
class PersonNode {
    private int no;
    private PersonNode next;

    @Override
    public String toString() {
        return "PersonNode{" +
                "no=" + no +
                '}';
    }
}


